// run: $exec < input
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int f[105000][20];
int n;

int gcd(int x,int y)
{
	if(x==0)return y;
	return gcd(y%x,x);
}


int getgcd(int l,int r)
{
	int j=31-__builtin_clz(r-l+1);
	return gcd(f[l][j],f[r-(1<<j)+1][j]);
}

int main()
{
	//for(int i=1;i<=20;i++)printf("%d %d\n",i,Log(i));
	int t;
	scanf("%d", &t);
	for (int ti = 1; ti <= t; ti++)
	{
		printf("Case #%d:\n", ti);
		scanf("%d", &n);
		for(int i=0;i<n;i++)scanf("%d",&f[i][0]);
		for(int j=1;j<=19;j++)
		{
			for(int i=0;i<n;i++)
			{
				if(i+(1<<j)-1<n)
				{
					f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
				}
			}
		}
		map<int,LL>mp;
		for(int i=0;i<n;i++)
		{
			int ed=i;
			while(ed<n)
			{
				int g=getgcd(i,ed);
				int l=ed,r=n-1;
				int m,tag=-1;
				while(l<=r)
				{
					if(r-l<=1)
					{
						if(getgcd(i,r)==g)tag=r;
						else tag=l;
						break;
					}
				 	m=(l+r)>>1;
					if(getgcd(i,m)==g)l=m;
					else r=m;
				}
				mp[g]+=tag-ed+1;
				ed=tag+1;
			}
		}
		int q;
		scanf("%d",&q);
		while(q--)
		{
			int l, r;
			scanf("%d%d",&l, &r);
			int ans=getgcd(l-1, r-1);
			printf("%d %lld\n",ans, mp[ans]);
		}
	}
}

